#include <iostream>
using namespace std;

void testO1(int n) {
  int time = 0;
  time += 1;
  cout << "O(1)=" << time << endl;
}

void testOlogn(int n) {
  int time = 0;
  for (int i = 1; i < n; i *= 2) {
    time += 1;
  }
  cout << "O(logn)=" << time << endl;
}

void testOn(int n) {
  int time = 0;
  for (int i = 1; i < n; ++i) {
    time += 1;
  }
  cout << "O(n)=" << time << endl;
}

void testOnlogn(int n) {
  int time = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 1; j < n; j *= 2) {
      time += 1;
    }
  }
  cout << "O(nlogn)=" << time << endl;
}

void testOn2(int n) {
  int time = 0;
  for (int i = 1; i < n; ++i) {
    for (int j = 1; j < n; ++j) {
      time += 1;
    }
  }
  cout << "O(n^2)=" << time << endl;
}

void testOm_n(int m, int n) {
  int time = 0;
  for (int i = 1; i < m; ++i) {
    time += 1;
  }
  for (int j = 1; j < n; ++j) {
    time += 1;
  }
  cout << "O(m+n)=" << time << endl;
}

void testOmn(int m, int n) {
  int time = 0;
  for (int i = 1; i < m; ++i) {
    for (int j = 1; j < n; ++j) {
      time += 1;
    }
  }
  cout << "O(mn)=" << time << endl;
}

void testOn_space(int n) {
  int* p = new int[n];
  for (int i = 0; i < n; ++i) {
    *(p + i) = i;
  }
  for (int i = 0; i < n; ++i) {
    cout << p[i] << ' ';
  }
  cout << "space O(n)=" << n << endl;
  delete[] p;
}

// 最好O(1)、最坏O(n)、平均(概率论)O(n)
int find(int arr[], int len, int n) {
  for (int i = 0; i < len; ++i) {
    if (arr[i] == n) return i;
  }
  return -1;
}

// 最好O(1)、最坏O(n)、平均(概率论)O(1)
// 均摊：每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1)
// 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1
// 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)
void insert(int array[], int length, int val) {
  static int count = 0;
  if (count == length) {
    int sum = 0;
    for (int i = 0; i < length; ++i) {
      sum = sum + array[i];
    }
    array[0] = sum;
    count = 1;
  }

  array[count] = val;
  ++count;
}

int main(int argc, const char* argv[]) {
  int n = 1 << 10;
  if (argc == 2) n = 1 << atoi(argv[1]);
  cout << "n=" << n << endl;

  // 常见时间复杂度：常量O(1) 对数O(logn) 线性O(n) 线性对数O(nlogn) 平方O(n^2)
  // 不常见时间复杂度：指数O(2^n) 阶乘O(n!)
  testO1(n);
  testOlogn(n);
  testOn(n);
  testOnlogn(n);
  testOn2(n);
  int m = n + 1;
  testOm_n(m, n);
  testOmn(m, n);

  // 常见空间复杂度：O(1) O(n) O(n^2)
  testOn_space(n);

  // 最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度（概率论）、均摊时间复杂度（特殊少见）
  const int SIZE = 1024;
  int arr[SIZE];
  for (int i = 0; i < SIZE; ++i) {
    arr[i] = i;
  }
  int idx = find(arr, SIZE, 443);
  std::cout << idx << endl;

  insert(arr, SIZE, 239);
  std::cout << arr[0] << endl;
}